import java.util.Arrays;

/**
 * 选择排序（Selection Sort）
 * 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。
 * 简单来说就是每次从待排序的数据中选择最小（或最大）的元素，并与已排序序列的末尾的最后一个元素交换，直到全部数据排序完成。
 *
 * @author Liu Yicong
 * @date 2025/9/21
 */
public class SelectionSort {
	public static Integer[] selectionSort(Integer[] arr) {

		if (arr == null || arr.length < 2) {
			return arr;
		}

		int n = arr.length;

		for (int i = 0; i < n - 1; i++) {
			int min = i;
			for (int j = i + 1; j < n; j++) {
				if (arr[min] > arr[j]) {
					min = j;
				}
			}

			if (i != min) {
				int t = arr[i];
				arr[i] = arr[min];
				arr[min] = t;
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		Integer[] data = {1, 8, 3, 9, 4, 5, 7, 2, 6};
		System.out.println(Arrays.toString(selectionSort(data)));
	}
}
